package leetcode.day_2021_03_8_2021_03_14;

import java.util.ArrayList;
import java.util.List;

/**
 * 52. N皇后 II
 * https://leetcode-cn.com/problems/n-queens-ii/
 */
public class LeetCode0052 {

    static int count = 0;
    public static int totalNQueens(int n) {
        StringBuilder str = new StringBuilder();
        for (int i=0; i<n; i++) {
            str.append('.');
        }
        List<String> list = new ArrayList<>();
        for (int i=0; i<n; i++) {
            list.add(str.toString());
        }
        backtrack(list, 0);
        return count;
    }

    public static void backtrack(List<String> list, int row) {
        if (row == list.size()) {
            count+=1;
            return;
        }
        int n = list.get(row).length();
        char[] demo = list.get(row).toCharArray();
        for (int col=0; col<n; col++) {
            if (!isValid(list, row, col)) {
                continue;
            }
            demo[col] = 'Q';
            list.set(row, new String(demo));
            backtrack(list, row+1);
            demo[col] = '.';
            list.set(row, new String(demo));
        }
    }

    public static boolean isValid(List<String> list, int row, int col) {
        int n = list.size();
        // 检查列是否存在Q
        for (int i=0; i<n; i++) {
            if(list.get(i).charAt(col) == 'Q')
                return false;
        }
        // 检查左上方是否存在Q
        for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if(list.get(i).charAt(j) == 'Q')
                return false;
        }
        // 检查右上方是否存在Q
        for(int i=row-1, j=col+1; i>=0&&j<list.size(); i--, j++) {
            if(list.get(i).charAt(j) == 'Q')
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        totalNQueens(4);
        System.out.println(count);
    }
}
